๋ฌธ์
๋ฟ์๋ฟ์์ ๋ฃฐ์ ๋ค์๊ณผ ๊ฐ๋ค.
ํ๋์ ์ฌ๋ฌ ๊ฐ์ง ์๊น์ ๋ฟ์๋ฅผ ๋๋๋ค. ๋ฟ์๋ ์ค๋ ฅ์ ์ํฅ์ ๋ฐ์ ์๋์ ๋ฐ๋ฅ์ด๋ ๋ค๋ฅธ ๋ฟ์๊ฐ ๋์ฌ ๋๊น์ง ์๋๋ก ๋จ์ด์ง๋ค. ๋ฟ์๋ฅผ ๋๊ณ ๋ ํ, ๊ฐ์ ์ ๋ฟ์๊ฐ 4๊ฐ ์ด์ ์ํ์ข์ฐ๋ก ์ฐ๊ฒฐ๋์ด ์์ผ๋ฉด ์ฐ๊ฒฐ๋ ๊ฐ์ ์ ๋ฟ์๋ค์ด ํ๊บผ๋ฒ์ ์์ด์ง๋ค. ์ด๋ 1์ฐ์๊ฐ ์์๋๋ค. ๋ฟ์๋ค์ด ์์ด์ง๊ณ ๋์ ์์ ๋ค๋ฅธ ๋ฟ์๋ค์ด ์๋ค๋ฉด, ์ญ์ ์ค๋ ฅ์ ์ํฅ์ ๋ฐ์ ์ฐจ๋ก๋๋ก ์๋๋ก ๋จ์ด์ง๊ฒ ๋๋ค. ์๋๋ก ๋จ์ด์ง๊ณ ๋์ ๋ค์ ๊ฐ์ ์์ ๋ฟ์๋ค์ด 4๊ฐ ์ด์ ๋ชจ์ด๊ฒ ๋๋ฉด ๋ ํฐ์ง๊ฒ ๋๋๋ฐ, ํฐ์ง ํ ๋ฟ์๋ค์ด ๋ด๋ ค์ค๊ณ ๋ค์ ํฐ์ง์ ๋ฐ๋ณตํ ๋๋ง๋ค 1์ฐ์์ฉ ๋์ด๋๋ค. ํฐ์ง ์ ์๋ ๋ฟ์๊ฐ ์ฌ๋ฌ ๊ทธ๋ฃน์ด ์๋ค๋ฉด ๋์์ ํฐ์ ธ์ผ ํ๊ณ ์ฌ๋ฌ ๊ทธ๋ฃน์ด ํฐ์ง๋๋ผ๋ ํ๋ฒ์ ์ฐ์๊ฐ ์ถ๊ฐ๋๋ค.
๋จ๊ท๋ ์ต๊ทผ ๋ฟ์๋ฟ์ ๊ฒ์์ ํน ๋น ์ก๋ค. ์ด ๊ฒ์์ 1:1๋ก ๋ถ๋ ๋์ ๊ฒ์์ด๋ผ ์ ์๋ ๊ฒ๋ ์ค์ํ์ง๋ง, ์๋๋ฐฉ์ด ํฐ๋จ๋ฆฐ๋ค๋ฉด ์ฐ์๊ฐ ๋ช ๋ฒ์ด ๋ ์ง ๋ฐ๋ก ํ์ ํ ์ ์๋ ๋ฅ๋ ฅ๋ ํ์ํ๋ค. ํ์ง๋ง ์์ง ์ค๋ ฅ์ด ๋ถ์กฑํ์ฌ ๋จ๊ท๋ ์๊ธฐ ํ๋์๋ง ์ ๊ฒฝ ์ฐ๊ธฐ ๋ฐ์๋ค. ์๋๋ฐฉ์ ํ๋๊ฐ ์ฃผ์ด์ก์ ๋, ์ฐ์๊ฐ ๋ช ๋ฒ ์ฐ์์ผ๋ก ์ผ์ด๋ ์ง ๊ณ์ฐํ์ฌ ๋จ๊ท๋ฅผ ๋์์ฃผ์!
์ ๋ ฅ
- ์ด 12๊ฐ์ ์ค์ ํ๋์ ์ ๋ณด๊ฐ ์ฃผ์ด์ง๋ฉฐ, ๊ฐ ์ค์๋ 6๊ฐ์ ๋ฌธ์๊ฐ ์๋ค. ์ด๋ .์ ๋น๊ณต๊ฐ์ด๊ณ .์ด ์๋๊ฒ์ ๊ฐ๊ฐ์ ์๊น์ ๋ฟ์๋ฅผ ๋ํ๋ธ๋ค. R์ ๋นจ๊ฐ, G๋ ์ด๋ก, B๋ ํ๋, P๋ ๋ณด๋ผ, Y๋ ๋ ธ๋์ด๋ค. ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋ ํ๋๋ ๋ฟ์๋ค์ด ์ ๋ถ ์๋๋ก ๋จ์ด์ง ๋ค์ ์ํ์ด๋ค. ์ฆ, ๋ฟ์ ์๋์ ๋น ์นธ์ด ์๋ ๊ฒฝ์ฐ๋ ์๋ค.
์ถ๋ ฅ
- ํ์ฌ ์ฃผ์ด์ง ์ํฉ์์ ๋ช์ฐ์๊ฐ ๋๋์ง ์ถ๋ ฅํ๋ค. ํ๋๋ ํฐ์ง์ง ์๋๋ค๋ฉด 0์ ์ถ๋ ฅํ๋ค.
๐ Logic
class Puyo {
char[][] field = new char[12][6];
int[] x_ary = { -1, 0, 1, 0 };
int[] y_ary = { 0, 1, 0, -1 };
List<Pair> remove;
Queue<Pair> queue;
int[][] visited;
...
}
- ๋ฟ์์ ํ๋๋ฅผ ๊ด๋ฆฌํ๊ธฐ ์ํ ํด๋์ค๋ฅผ ์์ฑํ๋ค.
public boolean searchChains();
- BFS๋ฐฉ์์ผ๋ก ํ๋์ ๋ฐ์๊ฐ๋ฅํ ์ฐ์๊ฐ ์๋์ง ํ์ํ๋ค.
- ํฐ์ง ์ ์๋ ๋ฟ์๋ฅผ
List<Puyo> remove์ ์ ์ฅํ์ฌ, ์ฐ์ ๋ฐ์ ์ ํด๋น ๋ฟ์๋ค์ ์ ๊ฑฐํ ์ ์๊ฒ ํ๋ค.
private void updateField();
- ์ฐ์ ํ์ ์ดํ, ๋ฐ์ํ ์ฐ์๊ฐ ์๋ ๊ฒฝ์ฐ์๋ง ํ๋๋ฅผ ์ ๋ฐ์ดํธํ๊ธฐ ์ํด ํธ์ถ๋๋ ๋ฉ์๋์ด๋ค.
๐ CODE
์ฝ๋ ๋ณด๊ธฐ/์ ๊ธฐ๐ซ
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
class Pair {
int x;
int y;
Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
class Puyo {
char[][] field = new char[12][6];
int[] x_ary = { -1, 0, 1, 0 };
int[] y_ary = { 0, 1, 0, -1 };
List<Pair> remove;
Queue<Pair> queue;
int[][] visited;
public boolean searchChains() {
remove = new LinkedList<>();
queue = new LinkedList<>();
visited = new int[12][6];
boolean pop = false;
for (int i = 11; i >= 0; i--) {
for (int j = 0; j < 6; j++) {
if (field[i][j] == '.') continue;
if (visited[i][j] != 0) continue;
char now = field[i][j];
int cnt = 1;
visited[i][j] = cnt++;
queue.add(new Pair(i, j));
remove.add(new Pair(i, j));
while(!queue.isEmpty()) {
Pair cur = queue.poll();
int curX = cur.x, curY = cur.y;
for (int t = 0; t < 4; t++) {
int ni = curX + x_ary[t], nj = curY + y_ary[t];
if (isBoundary(ni, nj)) continue;
if (visited[ni][nj] > 0) continue;
if (now == field[ni][nj]) {
visited[ni][nj] = cnt++;
queue.add(new Pair(ni, nj));
remove.add(new Pair(ni, nj));
}
}
}
if (cnt >= 5) {
pop = true;
for (Pair p : remove) {
field[p.x][p.y] = '.';
}
}
remove.clear();
}
}
if (pop) {
updateField();
}
return pop;
}
private void updateField() {
for (int i = 0; i < 6; i++) {
for (int j = 11; j > 0; j--) {
if (field[j][i] == '.') {
for (int k = j - 1; k >= 0; k--) {
if (field[k][i] != '.') {
field[j][i] = field[k][i];
field[k][i] = '.';
break;
}
}
}
}
}
}
private boolean isBoundary(int x, int y) {
return x < 0 | x > 11 | y < 0 | y > 5;
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line;
int chains = 0;
Puyo puyo = new Puyo();
for (int i = 0; i < 12; i++) {
line = br.readLine();
for (int j = 0; j < 6; j++) {
puyo.field[i][j] = line.charAt(j);
}
}
while(puyo.searchChains()) {
chains++;
}
System.out.println(chains);
br.close();
}
}
โ๏ธ Review
-
์ฃผ์ด์ง ์ํฉ์์, ๋จผ์ ์ฐ์๊ฐ ์ผ์ด๋ ์ ์๋์ง ํ์ ํ๋ค. ์ฌ๋ฌ ๊ฐ์ ์ฐ์๊ฐ ๊ฐ๋ฅํ๋ค๋ฉด, ์ด๋ ์ฐ์ ์์๋ก ์ฐ์๋ฅผ ๋ฐ์์ํฌ์ง๋ฅผ ๊ณ ๋ฏผํ๋ค.
- ์๊ฐํด๋ณด๋ ์ฐ์๊ฐ์ ์ฐ์ ์์๋ ์ค์ํ์ง ์์๊ณ , ์ฐ์ ๋ฐ์ ์ดํ ํด๋น ๋ฟ์๋ค์ ์ด๋ป๊ฒ ์ ๊ฑฐํ๋๊ฐ๊ฐ ๋ ์ค์ํ๋ค.
- ์ฐ์ ๋ฐ์ ๊ฐ๋ฅํ ๋ฟ์๋ค์ ํ์๊ณผ ๋์์ ์ ๊ฑฐํ ๋ฐฉ๋ฒ์ด ์๊ธฐ์ ๋ฆฌ์คํธ์ ์ ์ฅํ๋ฉด์ ์ฐ์๊ฐ ๋ฐ์ํ๋ ๊ฒฝ์ฐ์๋ง ์ด๋ฅผ ์ ๊ฑฐํ๋ ๋ฐฉ์์ ์ฐธ๊ณ ํ์ฌ ํด๊ฒฐํ๋ค.